#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=111121,inf=0x3f3f3f3f3f3f3f3f;
int n,a[100];
int fa[100],dep[100],ans;
vector<int>e[100];
int fp(int x,int p)
{
	int ans=1;
	while(p)
	{
		if(p&1)ans=ans*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ans;
}
void dfs(int x,int f)
{
	fa[x]=f;
	dep[x]=dep[f]+1;
	for ( auto v:e[x] )
	{
		if(v==f)continue;
		dfs(v,x);
	}
}
pair<int,int>get(int u,int v)
{
	pair<int,int>ans={a[u]&a[v],a[u]|a[v]};
	while(u!=v)
	{
		if(dep[u]<dep[v])swap(u,v);
		u=fa[u];
		ans.first&=a[u],ans.second|=a[v];
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	cin >>n;
	for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
	for ( int i = 1 ; i < n ; i++ )
	{
		int u,v;
		cin >>u >>v;
		e[u].push_back(v),e[v].push_back(u);
	}
	dfs(1,1);
	int ans=0;
	for ( int i = 1 ; i <= n ; i++ )
	{
		for ( int j = i ; j <= n ; j++ )
		{
			pair<int,int>res=get(i,j);
			ans+=fp(res.first,res.second);
			ans%=mod;
		}
	}
	cout <<ans;
	return 0;
}//20

